

package com.licw.zs.s397;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class p3 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<List<Integer>> lists = new ArrayList<>();
        lists.add(Arrays.asList(4, 3, 2));
        lists.add(Arrays.asList(3, 2, 1));
//        lists.add(Arrays.asList(6, 7, 14, 3));
//        lists.add(Arrays.asList(2, 5, 3, 1));
        int i = solution.maxScore(lists);
        System.out.println(i);

    }

    static
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxScore(List<List<Integer>> grid) {
            int m = grid.size(), n = grid.get(0).size();
            int[][] g = new int[m][];
            for (int i = 0; i < m; i++) {
                g[i] = grid.get(i).stream().mapToInt(a -> a).toArray();
            }
            int[][] dp = new int[m][n];
            // 从下往上
            for (int i = m - 1; i >= 0; i--) {
                //从右往左
                for (int j = n - 1; j >= 0; j--) {
                    update(g, i, j, dp);
                }
            }
            int ans = Integer.MIN_VALUE;
            for (int[] arr : dp) {
                for (int a : arr) {
                    ans = Math.max(ans, a);
                }
            }
            return ans;
        }

        private void update(int[][] grid, int x, int y, int[][] dp) {
            int m = grid.length, n = grid[0].length;
            int res = Integer.MIN_VALUE;
            for (int i = x + 1; i < m; i++) {
                res = Math.max(res, grid[i][y] - grid[x][y] + Math.max(0, dp[i][y]));
            }
            for (int i = y + 1; i < n; i++) {
                res = Math.max(res, grid[x][i] - grid[x][y] + Math.max(0, dp[x][i]));
            }
            dp[x][y] = res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}